#include <iostream>
#include <map>
#include <vector>

using std::map;
using std::vector;

class Solution
{
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        // 让时间复杂度降到n方
        int count = 0;
        map<int, int> m;
        // 将前两个数组放在map中
        for (size_t i = 0; i < nums1.size(); ++i)
        {
            for (size_t j = 0; j < nums2.size(); ++j)
            {
                ++m[nums1[i] + nums2[j]];
            }
        }

        for (size_t i = 0; i < nums3.size(); ++i)
        {
            for (size_t j = 0; j < nums4.size(); ++j)
            {
                int sum = nums3[i] + nums4[j];
                if (m.count((0 - sum)) != 0)
                {
                    // 找到了
                    count += m[(0 - sum)];
                }
            }
        }
        return count;
    }
};
